/*
Date:20210423 9:46am

key:像这种集合里很多元素由累x得出的，很多都是动态规划，乘法因子到结果的状态转移。
这里就是从后往前第一个能除的dp+1.
*/
class Solution {
public:
    int T(vector<int>&v,int&a,int*dp)
    {
        //能除里面最大的
        int max_i=-1;
        int max=0;
        for(int i=a-1;i>=0;i--)
        {
            if(v[a]%v[i]==0)
            {
                if(dp[i]>max)
                {
                    max=dp[i];
                    max_i=i;
                }
                
            }
        }
        return max_i;
    }
    void F(vector<int>&v,vector<int>& nums,int j,int*dp)
    {
        v.push_back(nums[j]);
        for(int r=j-1;r>=0;r--)
        {
            //保证相邻的能除，相邻dp差1
            if((nums[j]%nums[r]==0&&dp[j]-1==dp[r]))
            {
                v.push_back(nums[r]);
                dp[j]--;
                nums[j]=nums[r];
            }
        }

    }
    vector<int> largestDivisibleSubset(vector<int>& nums) 
    {
        set<vector<int>>S;
        vector<int>v;
        int *dp=new int[nums.size()];
        dp[0]=1;
        sort(nums.begin(),nums.end());
        //
        int tmp;
        int max=0;
        int max_i;
        for(int i=0;i<nums.size();i++)
        {
            tmp=T(nums,i,dp);
            if(tmp!=-1)
            {
                
                dp[i]=dp[tmp]+1;
                
                if(dp[i]>max)
                {
                    max=dp[i];
                    max_i=i;
                }
            }
            else
            {
                dp[i]=1;
            }
        }
        //
        vector<int>answer;
        //v.push_back(nums[max_i]);
        F(answer,nums,max_i,dp);
        return answer;
    }
};